from typing import List


class Solution:
    """
    方法：回溯算法
    Args:
        s: str - 输入的字符串
    Returns:
        List[List[str]] - 所有可能的回文分割
    Time: O(n * 2^n) - 共有2^n个分割，每个分割需要O(n)时间复制
    Space: O(n) - 递归栈深度为n，path数组长度为n
    """
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)
        def backtrack(i: int) -> None:
            if i == n:
                ans.append(path.copy())
                return
            for j in range(i, n):
                t = s[i:j+1]
                if t == t[::-1]:
                    path.append(t)
                    backtrack(j+1)
                    path.pop()
        backtrack(0)
        return ans